package _11_整理题目._7_查找排序;

import org.junit.Test;

/**
 * https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/
 * 
 * 在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
 * 请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
 * 
 * 1 2 3
 * 4 5 6
 * 7 8 9
 * 
 * 思路：
 * 根据二维数组的有序性，从右上角看，可以看做是一个搜索树
 * 所以首先定位到右上角，然后出发，比较，移动
 * 
 */
public class _01_二维数组中查找 {
    
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if(matrix==null || matrix.length==0) return false;
        int m = matrix.length, n = matrix[0].length;
        int i = 0, j = n-1;
        while(i<=m-1 && j>=0) {
            if(target > matrix[i][j]) {
                i++;
            } else if(target < matrix[i][j]) {
                j--;
            } else {
                return true;
            }
        }
        return false;
    }
    
    @Test
    public void main() {
        int[][] matrix = {  {1, 2, 3},
                            {4, 5, 6},
                            {7, 8, 9}};
        System.out.println(findNumberIn2DArray(matrix, 5));
    }
}
